"""
leetcode 863

给定一个二叉树（具有根结点 root）， 一个目标结点 target ，和一个整数值 K 。

返回到目标结点 target 距离为 K 的所有结点的值的列表。 答案可以以任何顺序返回。

首先是 题目里给了target节点的引用 是可以直接访问到target节点的 而不需从root节点开始遍历树来搜索target节点

其次 正常模拟思路就是 从target节点开始一层层向外扩展 知道距离为K

这里为了能达到向往扩展  这里使用了一个trick  就是对子节点添加指向父节点的引用
"""
class Solution(object):
    def distanceK(self, root, target, K):
        def dfs(node, par = None):
            if node:
                node.par = par
                dfs(node.left, node)
                dfs(node.right, node)

        dfs(root)  # 递归添加子节点对父节点的引用， 这样树就变成了无向图了 可以使用BFS不断扩展

        queue = collections.deque([(target, 0)])
        seen = {target}
        while queue:
            if queue[0][1] == K:
                return [node.val for node, d in queue]
            node, d = queue.popleft()
            for nei in (node.left, node.right, node.par):
                if nei and nei not in seen:
                    seen.add(nei)
                    queue.append((nei, d+1))

        return []
